/*
Date:20210521 10:00AM
key:1.三大经典动态规划可以说是三大方向的代表
    (散乱)最长(数组内乱序,乱序就不存在串)连续递增子序列
    (数组紧凑)最长(按数组序)连续递增子序列(当前)以nums[i]为结尾(300. 最长递增子序列
    (数字紧凑)最长(按数组序)连续递增子串,也是以nums[i]为结尾，但只需要判断num[i-1]是否大于nums[i]-1。(674. 最长连续递增序列

*/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int n=nums.size();
        int*dp=new int[n];
        dp[0]=1;
        int Max;
        for(int i=1;i<n;i++)
        {
            Max=INT_MIN;
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {
                    Max=max(Max,dp[j]);
                }
            }
            //假如当前nums[i]是已知最小的，那么dp[i]只能是1
            if(Max==INT_MIN)
            {
                dp[i]=1;
            }
            else
            {
                dp[i]=Max+1;
            }
            
        }
        // for(int i=1;i<n;i++)
        // {
        //     cout<<dp[i]<<" ";
        // }
        //根据定义 以某个为末尾的最大长度 因此要遍历dp
        return *max_element(dp,dp+n);
    }

};